package com.zjoin.study.arithmetic.基础.数组;

/**
 * 类名 旋转数组
 * 描述
 *
 * @Author xwyang
 * @Date 2020/8/14 16:59
 * @Version 1.0
 **/
public class 旋转数组 {

    /*题设
    给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     */
    
    /**
     * 输入: [1,2,3,4,5,6,7] 和 k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右旋转 1 步: [7,1,2,3,4,5,6]
     * 向右旋转 2 步: [6,7,1,2,3,4,5]
     * 向右旋转 3 步: [5,6,7,1,2,3,4]
     * 1,2,3,4,5,6,7,8,9
     * 7,8,9, 1,2,3,4,5,6    9-2*3=3 6-3=3
     * 6,7,8,9, 1,2,3,4,5    9-2*4=1 5-4=1
     * 5,6,7,8,9, 1,2,3,4    9-2*5=-1 4-5=-1
     */
    public static void rotate(int[] nums, int k) {
        if (nums.length < 2 || k <= 0) {
            return;
        }
        k = k % nums.length;
        if (k == 0) {
            return;
        }
        if (k * 2 > nums.length) {
            rotate1(nums, k, 0, nums.length);
        } else {
            rotate2(nums, k, 0, nums.length);
        }
        print(nums);
    }
    
    public static void rotate1(int[] nums, int k, int s, int l) {
        System.out.println("************************************");
        int x = l - k;
        x = Math.min(x, k);
        int z = x == 0 ? 1 : (l - s) / x - 1;
        System.out.print("待交换数组：");
        print(nums, s, l);
        print(nums);
        System.out.println();
        for (int t = 0 * x; t < z; t++) {
            for (int i = s + (x * t); i < s + x * (t + 1); i++) {
                int r = nums[i];
                nums[i] = nums[i + x];
                nums[i + x] = r;
            }
            System.out.print("交换后数组：");
            print(nums, s, l);
        }
        int mod = x == 0 ? 1 : (l-s) % x;
        if (mod > 0) {
            System.out.println("剩余" + x + "个数后移" + mod + "位");
            rotate2(nums, mod, l - (mod + x), l);
            
        }
    }
    
    public static void rotate2(int[] nums, int k, int s, int e) {
        System.out.println("=================================");
//        待交换数组：1 2 3 16 17
        int t = (e - s) / k;
        System.out.print("待交换数组：");
        print(nums, s, e);
        System.out.println();
        
        for (int i = 0; i < t - 1; i++) {
            for (int j = e - (i * k) - 1; j > e - k * (i + 1) - 1; j--) {
                int r = nums[j];
                nums[j] = nums[j - k];
                nums[j - k] = r;
            }
            System.out.print("交换后数组：");
            print(nums, s, e);
        }
        int mod = (e - s) % k;
        if (mod > 0) {
            System.out.println("剩余" + mod + "个数前移" + k + "位");
            rotate1(nums, mod, (s), (s + k + mod));
        }
    }
    
    
    private static void print(int[] nums) {
        for (int c : nums) {
            System.out.print(c + ",");
        }
        System.out.println();
    }
    
    
    private static void print(int[] nums, int s, int l) {
        for (int i = s; i < l; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
        print(nums);
        System.out.println();
        
        rotate(nums, 8);
        
    }
    
    /**
     * 推荐算法
     * 这个方法基于这个事实：当我们旋转数组 k 次，
     * k\%nk%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
     *
     * 在这个方法中，我们首先将所有元素反转。
     * 然后反转前 k 个元素，再反转后面 n-kn−k 个元素，就能得到想要的结果。
     *
  
     * @param nums
     * @param k
     */
    public void rotate3(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    
    
    
}
